package com.yoshino.leetcode.oneHundred.forth;

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> intsets = new HashSet<>();
        for (int num : nums) {
            if (!intsets.add(num)) {
                return num;
            }
        }
        return -1;
    }

    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] == target) {
                l = r = mid;
                while (l >= 0 && nums[l] == target){l--;}
                while (r < nums.length && nums[r] == target){r++;}
                return r - l - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return 0;
    }

    public int missingNumber(int[] nums) {
        int n = nums.length;
        // 递增数组，二分法
        if (n < 1) {
            return 1;
        }
        if (nums[n - 1] == n - 1) {
            return n;
        }
        int l = 0, r = n - 1, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] == mid) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}